package com.yequan.leetcode.recursion.climbstairs;

/**
 * @author yequan
 * @date 2021/10/16 21:17
 **/
public class RecodeClimbStairs2 {

    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    public int climbStairs2(int n) {
         int[] cache = new int[n+1];
         return helper(n, cache);
    }

    private int helper(int n, int[] cache) {
        if (n <= 2){
            return n;
        }
        if (cache[n] > 0){
            return cache[n];
        }
        cache[n] = helper(n-1, cache) + helper(n-2, cache);
        return cache[n];
    }

}
